package leetcode.code0236;

import leetcode.helper.tree.TreeNode;

public class Solution236 {
	class Info {
		int has;
		TreeNode ancestor;

		public Info(int has, TreeNode ancestor) {
			super();
			this.has = has;
			this.ancestor = ancestor;
		}

	}

	public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
		return this.f(root, p, q).ancestor;
	}

	private Info f(TreeNode root, TreeNode p, TreeNode q) {
		if (root == null) {
			return new Info(0, null);
		}
		Info left = this.f(root.left, p, q);
		if (left.ancestor != null) {
			return left;
		}
		Info right = this.f(root.right, p, q);
		if (right.ancestor != null) {
			return right;
		}
		int has = root.val == p.val || root.val == q.val ? 1 : 0;
		has += left.has;
		has += right.has;
		TreeNode ancestor = has == 2 ? root : null;
		return new Info(has, ancestor);
	}
}
